package com.dmall.heap;

import com.dmall.array.Array;

/**
 * 最大堆：使用动态数组模拟二叉堆
 * 最大堆的特点：其父节点的值总是大于其子节点的值
 * @param <E>
 * @date 2019-08-19 22:29:41
 * @author xiao1.wang@dmall.com
 */
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MaxHeap() {
        this(10);
    }

    public MaxHeap(E[] arr) {
        data = new Array(arr);
        for (int i = parent(data.getSize() - 1); i >= 0; i--) {
            shiftDown(i);
        }
    }

    public int size() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return 2 * index + 1;
    }

    private int rightChild(int index) {
        return 2 * index + 2;
    }

    public void add(E e) {
        data.addLast(e);
        shiftUp(data.getSize() - 1);
    }

    private void shiftUp(int index) {
        while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0) {
            data.swap(index, parent(index));
            index = parent(index);
        }
    }

    public E extractMax() {
        E result = findMax();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        shiftDown(0);
        return result;
    }

    private void shiftDown(int index) {
        while (leftChild(index) < data.getSize()) {
            int maxChildIndex = leftChild(index);
            if (rightChild(index) < data.getSize() && data.get(maxChildIndex).compareTo(data.get(rightChild(index))) < 0) {
                maxChildIndex ++;
            }
            if (data.get(index).compareTo(data.get(maxChildIndex)) >= 0) {
                break;
            }
            data.swap(index, maxChildIndex);
            index = maxChildIndex;
        }
    }

    public E findMax() {
        if(data.getSize() == 0) {
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        }
        return data.get(0);
    }

    /**
     * 由于最大堆取出元素时总是取出最大的元素，所以replace方法的作用就是：
     * 将新的元素方法根的位置，然后下沉就可以了
     * @param newElement
     * @return
     */
    public E replace(E newElement) {
        E ret = findMax();
        data.set(0, newElement);
        shiftDown(0);
        return ret;
    }
}
